package main

import (
	"fmt"
	"sort"
)

//#link: https://leetcode-cn.com/problems/time-based-key-value-store/
func main() {
	obj := Constructor()
	obj.Set("love", "high", 10)
	obj.Set("love", "low", 20)

	fmt.Println(obj.Get("love", 5))
	fmt.Println(obj.Get("love", 10))
	fmt.Println(obj.Get("love", 15))
	fmt.Println(obj.Get("love", 20))
	fmt.Println(obj.Get("love", 25))

}

type TimeMap struct {
	score map[string][]int          //用来记录key与时间戳的关系
	value map[string]map[int]string //用来记录key和 value和时间戳的关系
}

/** Initialize your data structure here. */
func Constructor() TimeMap {
	return TimeMap{
		value: make(map[string]map[int]string),
		score: make(map[string][]int),
	}
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
	if v, ok := this.value[key]; ok {
		v[timestamp] = value
	} else {
		valueMap := make(map[int]string)
		valueMap[timestamp] = value
		this.value[key] = valueMap
	}
	this.score[key] = append(this.score[key], timestamp)
}

func (this *TimeMap) Get(key string, timestamp int) string {
	//先根据timestamp获取最近的时间段
	if v, ok := this.value[key]; ok {
		timestamps := this.score[key]
		index := sort.SearchInts(timestamps, timestamp)
		if index == 0 && timestamp != timestamps[0] {
			return ""
		}
		if index == len(timestamps) || index == len(timestamps)-1 && timestamps[index] != timestamp {
			index -= 1
		}
		return v[timestamps[index]]
	} else {
		return ""
	}
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Set(key,value,timestamp);
 * param_2 := obj.Get(key,timestamp);
 */
